#include <iostream>
#include <fstream>
#include <sstream>

#include <string>

#include <map>
#include <list>
#include <set>

#include <boost/tokenizer.hpp>

#include "expansion_graph.h"
#include "expansion_graph_instance.h"
#include "string_vertex_edge.h"
#include "list_ops.h"
#include "instance_isomorphism.h"


bool read(char filename[],
          std::map<ExpansionGraph<StringVertexEdge, StringVertexEdge>*, int> &graphs,
          std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > *parent_instance_list)
{
  // File 
  std::string line;
  std::ifstream input_file(filename);
  
  // Tokenizing
  typedef boost::tokenizer<boost::char_separator<char> > tokenizer;
  boost::char_separator<char> sep(" ");
  
  if (input_file.is_open())
    {
      ExpansionGraph<StringVertexEdge, StringVertexEdge> *curr_graph;
      std::map<int, StringVertexEdge*> *curr_graph_map;
      bool dirty = false;
      int graph_count = -1;
      int edge_count = 0;

      while (! input_file.eof() )
        {
          std::getline(input_file,line);
          
          tokenizer tokens(line, sep);
          
          tokenizer::iterator tok_iter = tokens.begin();
         
          
          if (tok_iter != tokens.end())
            {
              if (*tok_iter == "XP")
                {
                  if(dirty)
                    {
                    graphs.insert(std::pair<ExpansionGraph<StringVertexEdge, StringVertexEdge>*, int>(curr_graph, graph_count));
                    delete curr_graph_map;
                    }
                  
                  dirty = true;
                  graph_count++;
                  edge_count = 0;

                  curr_graph = new ExpansionGraph<StringVertexEdge, StringVertexEdge>();
                  curr_graph_map = new std::map<int, StringVertexEdge*>;

                }
              else if (*tok_iter == "v")
                {
                  tok_iter++;
                  std::istringstream iss(*tok_iter);
                  int id;
                  iss >> id;

                  tok_iter++;
                  std::string payload_data = *tok_iter;
                  
                  StringVertexEdge *curr_vertex = new StringVertexEdge(id, payload_data);
                  curr_graph->add_vertex(curr_vertex);
                  curr_graph_map->insert(std::pair<int, StringVertexEdge*>(id, curr_vertex));
                  
                }
              else if (*tok_iter == "u")
                {
                  edge_count++;

                  tok_iter++;
                  std::istringstream iss1(*tok_iter);
                  int id1;
                  iss1 >> id1;

                  tok_iter++;

                  std::istringstream iss2(*tok_iter);
                  int id2;
                  iss2 >> id2;

                  tok_iter++;
                  std::string payload_data = *tok_iter;

                  StringVertexEdge *curr_edge = new StringVertexEdge(edge_count, payload_data);
                  
                  curr_graph->add_edge(curr_edge,
                                       (curr_graph_map->find(id1))->second,
                                       (curr_graph_map->find(id2))->second);

                  ExpansionGraphInstance<StringVertexEdge, StringVertexEdge> *curr_instance = new ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>(curr_graph);
                  curr_instance->add_vertex((curr_graph_map->find(id1))->second);
                  curr_instance->add_vertex((curr_graph_map->find(id2))->second);
                  curr_instance->add_edge(curr_edge);
                  curr_instance->update_canonical_label(curr_instance->get_expansion_order());
                  parent_instance_list->push_back(curr_instance);

                }
            }
        }
      
      if(dirty)
        {
          graphs.insert(std::pair<ExpansionGraph<StringVertexEdge, StringVertexEdge>*, int>(curr_graph, graph_count));
          delete curr_graph_map;
        }
      input_file.close();
      return true;
    }	    
  else 
    return false;
}

int main (int argc, char *argv[])
{

  std::istringstream iss(argv[2]);
  int depth;
  iss >> depth;

  std::istringstream iss2(argv[3]);
  int frequency;
  iss2 >> frequency;
  
  std::map<ExpansionGraph<StringVertexEdge, StringVertexEdge>*, int> graphs;
  std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > *parent_instance_list = new std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >;
  std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > *frequent_instance_list = new std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >;


  read(argv[1], graphs, parent_instance_list);


  int feature_count = 0;

  for(int depth_counter = 0; depth_counter < depth; depth_counter++) 
    {
      
      std::map<std::string, std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > > *canonical_dict = new std::map<std::string, std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > >;
      
      for(std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >::iterator i = parent_instance_list->begin();
          i != parent_instance_list->end();
          i++)
        {
          std::string curr_canonical_label;
          curr_canonical_label = (*i)->get_canonical_label();
          ((*canonical_dict)[curr_canonical_label]).insert(*i);
        }
      
      std::set<std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > > partioned;

      for(std::map<std::string, std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > >::iterator i = canonical_dict->begin();
          i != canonical_dict->end();
          i++)
        partioned.insert(i->second);
      
      delete canonical_dict;

      for(std::set<std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > >::iterator i = partioned.begin();
          i != partioned.end();
          i++)
        {

          std::multiset<ExpansionGraph<StringVertexEdge, StringVertexEdge>* > *current_feature = new std::multiset<ExpansionGraph<StringVertexEdge, StringVertexEdge>* >;
          std::set<ExpansionGraph<StringVertexEdge, StringVertexEdge>* > *current_feature_unique = new std::set<ExpansionGraph<StringVertexEdge, StringVertexEdge>* >;
          
          for(std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >::iterator j = i->begin();
              j != i->end();
              j++)
            {
              ExpansionGraph<StringVertexEdge, StringVertexEdge> *curr_graph;
              (*j)->get_graph(&curr_graph);
              current_feature->insert(curr_graph);
              current_feature_unique->insert(curr_graph);
            }


          if ((current_feature_unique->size()) >= frequency)
            {
              feature_count++;
              
              for(std::set<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >::iterator j = i->begin();
                  j != i->end();
                  j++)
                frequent_instance_list->push_back(*j);
            
            }
                

 //          for(std::set<ExpansionGraph<StringVertexEdge, StringVertexEdge>* >::iterator j = current_feature_unique->begin();
//               j != current_feature_unique->end();
//               j++)
//             std::cout << (graphs.find(*j))->second << " " << feature_count << " " << current_feature->count(*j) << "\n";
 
          delete current_feature;
          delete current_feature_unique;
        }

       ExpansionGraphInstanceUniqueExpansion<StringVertexEdge, StringVertexEdge> expansion;
       std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* > *child_instance_list = new std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >;

       expand(frequent_instance_list, child_instance_list, expansion);

      for(std::list<ExpansionGraphInstance<StringVertexEdge, StringVertexEdge>* >::iterator i = parent_instance_list->begin();
          i != parent_instance_list->end();
          i++)
        delete *i;  
      delete parent_instance_list;

      frequent_instance_list->erase(frequent_instance_list->begin(), frequent_instance_list->end());

      parent_instance_list = child_instance_list;

      std::cout << "Expanding " << parent_instance_list->size() << " instances.\n"; 
    }

  for(std::map<ExpansionGraph<StringVertexEdge, StringVertexEdge>*, int>::iterator j = graphs.begin();
      j != graphs.end();
      j++)
      delete j->first;

      std::cout << "Found " << feature_count << " frequent subgraphs.\n"; 

  return 0;
}
